67. Add Binary

題目

Given two binary strings a and b, return their sum as a binary string.

Example 1:

Input: a = "11", b = "1"
Output: "100"

Example 2:

Input: a = "1010", b = "1011"
Output: "10101"

Constraints:

• 1 <= a.length, b.length <= 104
• a and b consist only of '0' or '1' characters.
• Each string does not contain leading zeros except for the zero itself.

解法(Java)

這就是基本的陣列從尾端進行加總，最後如果有需要進位再重新建立新陣列，不過這邊有嘗試新方法，因為它是字串，可以先建立長度+1的陣列，最後再取子字串。

Runtime: 1 ms (100%)
Memory Usage: 41.1 MB (73.06%)

class Solution {
    public String addBinary(String a, String b) {
        char[] ac = a.toCharArray(), bc = b.toCharArray();

        int carry = 0, acl = ac.length, bcl = bc.length;
        char[] result = new char[(acl > bcl ? acl : bcl) + 1];
        for (int i = result.length - 1; i >= 0; i--) {
            if (acl > 0 && bcl > 0) {
                carry = (ac[--acl] + bc[--bcl] + carry) % 48;
            } else if (acl > 0 && bcl <= 0) {
                carry = (ac[--acl] + carry) % 48;
            } else if (acl <= 0 && bcl > 0){
                carry = (bc[--bcl] + carry) % 48;
            }

            if (carry > 1) {
                result[i] = carry == 2 ? '0' : '1';
                carry = 1;
            } else {
                result[i] = carry == 1 ? '1' : '0';
                carry = 0;
            }
        }

        String str = new String(result);
        if (result[0] == '0') {
            return str.substring(1);
        } else {
            return str;
        }
    }
}

Implement strStr()

題目

Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

Input: haystack = "sadbutsad", needle = "sad"
Output: 0
Explanation: "sad" occurs at index 0 and 6.
The first occurrence is at index 0, so we return 0.

Example 2:

Input: haystack = "leetcode", needle = "leeto"
Output: -1
Explanation: "leeto" did not occur in "leetcode", so we return -1.

Constraints:

• 1 <= haystack.length, needle.length <= 10^4
• haystack and needle consist of only lowercase English characters.

解法(Java)

這題在LeetCode Problem 找不到，應該是只有在Explore Card 有的題目，不過也很簡單，只要判斷子字串在主字串的起始位置就好了。

Runtime: 0 ms (100%%)
Memory Usage: 40.2 MB (74.75%)

class Solution {
    public int strStr(String haystack, String needle) {
        char[] haystackChar = haystack.toCharArray(), needleChar = needle.toCharArray();
        int haystackSize = haystackChar.length, needleSize = needleChar.length;
        if (haystackSize < needleSize) return -1;

        int i, j;
        for (i = 0; i < haystackSize; i++) {
            if (haystackSize - i < needleSize) break;

            if (haystackChar[i] == needleChar[0]) {
                for (j = 0; j < needleSize; j++) {
                    if (haystackChar[i + j] != needleChar[j]) break;
                }
                if (j == needleSize) return i;
            }
        }

        return -1;
    }
}

14. Longest Common Prefix

題目

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

Input: strs = ["flower","flow","flight"]
Output: "fl"

Example 2:

Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Constraints:

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] consists of only lowercase English letters.

解法(Java)

這邊Java 可以使用StringBuilder 去組答案，只要從頭開始遍歷就可以了，如果中間有比較短的字串就catch 例外不處理。

Runtime: 1 ms (82.93%)
Memory Usage: 39.9 MB (91.19%)

class Solution {
    public String longestCommonPrefix(String[] strs) {
        int size = strs.length;
        if (size == 1) return strs[0];

        StringBuilder sb = new StringBuilder();

        char temp;
        int firstSize = strs[0].length(), i = 0, j = 1;
        try {
            for (i = 0; i < firstSize; i++) {
                temp = strs[0].charAt(i);
                for (j = 1; j < size; j++) {
                    if (temp != strs[j].charAt(i)) break;
                }
                if (j != size) break;
                else sb.append(temp);
            }
        } catch (StringIndexOutOfBoundsException e) {
            // to nothing
        }

        return sb.toString();
    }
}